package xoroperation;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2023-01-10
 * Time: 0:57
 */
//数组中有一种数出现了k次，其他数出现了m次，m>1,k<m;
    //那么找到这个出现k次的数
    //空间复杂度为o(1)，时间复杂度o(n)
public class KMTimes {
    public static  int  kmTimes(int[] arr,int k,int m){
        int[] t=new int[32];
        for(int i=0;i<32;i++){
            for(int num:arr){
                //统计num的二进制的1的个数，看二进制分布形式
                t[i]+=(num>>i) &1;
            }
        }
        //最终的答案
        int res=0;
        for(int i=0;i<32;i++){
            if(t[i]%m!=0){ //出现k次的数第i位置有1
                //说明二进制这个i位置，出现k次的数也是有的，不止是m次的数
                //找到了出现1的位置只需要把k的二进制分布还原出来即可，就让它跟1左移i位的结果按位或运算即可
                res|=(1<<i);
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        int[] arr={2,2,3,3,3,4,4,4,6,6,6};
        System.out.println(kmTimes(arr, 2, 3));
    }
}
